package class01;

/**
 * 算法: 有具体的问题 有设计解决这个问题的具体流程 有评价处理流程的可量化指标
 *
 * 算法分类: 明确知道怎么算的流程 明确知道怎么尝试的流程
 *
 * 数据结构:
 * 连续结构(数组)
 * 跳转结构(链表, 实际是持有其他对象的地址)
 * 连续+跳转结构(组合, map是数组+链表, 达到一定阈值链表转换为树以降低查询深度)
 *
 * 时间复杂度:
 * 常数时间操作: 与数据量无关操作
 * 复杂度只关心"操作次数与数据量函数"的最高阶
 * 数据量N -> 无穷大时, 最高阶影响最大
 *
 *
 *
 * 冒泡排序: O(N^2)
 * 二分: O(log N)
 *
 */
public class Code01_PrintBinary {

  public static void print(int num) {
    // 每次与向左位移i位的 1 进行与运算(&), 结果为 1 则打印 1
    // 为保证正序输出
    for (int i = 31; i >= 0; i--) {
      System.out.print((num & (1 << i)) == 0 ? "0" : "1");
    }
    System.out.println();
  }

  public static void main(String[] args) {
    // int 有 32位, 首位为符号位, 0 为正数, 1 为负数
    System.out.println("---------------- 正负 ----------------");
    print(0);
    int num = 4;
    // 00000000000000000000000000000100
    print(num);
    // 首位符号位( + - ), 后31位取反再加一
    // 为了 + - * / 在处理正负数时能只用一套逻辑(负数为正数后31位取反再加一)
    // 11111111111111111111111111111100
    print(-num);
    // 取反, 符号位也会参与
    print(~(-num));
    print(~(-num) + 1);

    System.out.println();
    System.out.println("---------------- 值域 ----------------");
    // 值域为 2^31 -1, 2147483647 (正数被 0 占了一位)
    System.out.println(Integer.MAX_VALUE);
    // 01111111111111111111111111111111
    print(Integer.MAX_VALUE);
    // -2147483648
    System.out.println(Integer.MIN_VALUE);
    // 10000000000000000000000000000000
    print(Integer.MIN_VALUE);

    System.out.println();
    System.out.println("---------------- |&^ ----------------");

    print(4);
    print(6);
    print(4 | 6);
    print(4 & 6);
    print(4 ^ 6);

    System.out.println();
    System.out.println("---------------- >> ----------------");
    print(Integer.MIN_VALUE);
    // 带符号位移
    print(Integer.MIN_VALUE >> 1);
    // 不带符号位移
    print(Integer.MIN_VALUE >>> 1);

    System.out.println();
    System.out.println("---------------- ~ ----------------");
    print(1);
    // - 号
    print(-1);
    // - 号可以表示为 ~(数值) + 1
    print(~(1) + 1);

    System.out.println();
    System.out.println("---------------- min ----------------");
    // int最小值取反再加1, 最后值还是int最小值
    print(Integer.MIN_VALUE);
    print(~Integer.MIN_VALUE);
    print(~(Integer.MIN_VALUE) + 1);
    print(0);
    print(~(0) + 1);
  }
}
